Modern computing applications require storage of large amounts of data. Over time, the need to storage and retrieve large amounts of data continues to increase. Other common concerns are the ability to store data durably and efficiently. Durability typically refers to the ability to recover data in the event of a failure. Data durability typically requires some form of redundancy in how the data is stored. For example, data may be mirrored to two different storage devices such that an exact replica copy of the data is stored on both storage devices. If one of the storage devices fails, the data can still be retrieved from the other storage device. Some systems desire even stronger levels of durability that involve more complex redundancy encoding scheme that allow the data to still be retrieved even after multiple device failures. Techniques to provide data durability typically incur some amount of overhead, both in terms of the amount of additional storage required and computational overhead, and thus are at odds with the desire to be able to store and retrieve large amounts of data efficiently.
Web-based applications, cloud computing, and other network and Internet based technologies are areas frequently requiring storage of large amounts of data with needs for durability and efficiency. The conventional Web model allows clients to access Web resources (e.g., applications, services and data) via an HTTP client program, such as a Web browser. A technology referred to as Web services has been developed to provide programmatic access to Web resources. Web services may be used to provide programmatic access to Web resources including technology platforms (e.g., applications and services) and data (e.g., product catalogs and other databases) hosted on Web-connected computers such as Web server systems via a Web service interface. Generally speaking, a Web service interface may be configured to provide a standard, cross-platform API (Application Programming Interface) for communication between a client requesting some service to be performed and the service provider. In some implementations, a Web service interface may be configured to support the exchange of documents or messages including information describing the service request and response to that request. Such documents, or messages, may be exchanged using standardized Web protocols, such as the Hypertext Transfer Protocol (HTTP), for example, and may be formatted in a platform-independent data format, such as eXtensible Markup Language (XML), for example.
One example of a service that is provided to clients via a Web service interface is a virtual computing service. The advent of virtualization technologies for commodity hardware has provided benefits with respect to managing large-scale computing resources for many clients with diverse needs, allowing various computing resources to be efficiently and securely shared by multiple clients. For example, a virtual computing service may allow a single physical computing machine to be shared among multiple users by providing each user with one or more virtual machines hosted by the single physical computing machine, with each such virtual machine being a software simulation acting as a distinct logical computing system that provides users with the illusion that they are the sole operators and administrators of a given hardware computing resource, while also providing application isolation and security among the various virtual machines. Furthermore, some virtualization technologies are capable of providing virtual resources that span two or more physical resources, such as a single virtual machine with multiple virtual processors that spans multiple distinct physical computing systems. With virtualization, the single physical computing device can create, maintain or delete virtual machines in a dynamic manner. In turn, users can request computer resources from a data center and be provided with varying numbers of virtual machine resources on an “as needed” basis or at least on an “as requested” basis. In some systems, virtualized computing resources can be used to implement virtual desktops.
Another example of a service that is provided to clients via a Web service interface is a data storage service. A typical data storage service (which may be referred to herein as an “object-redundant storage system”) may receive requests to store data objects on behalf of storage service clients, and may store those data objects using redundancy in order to provide a high level of durability for the stored data. For example, such a data storage service may replicate the objects it stores across different storage nodes to increase the likelihood that object data will survive the failure of any given storage node. In such systems, until a certain minimum number of replicas (e.g., two or three) of an object have been successfully written the write operation may not be considered to be completed. However, for a given object, the actual number of valid replicas (or instances) of that object might at some points in time be less than the target number, for a variety of reasons, and a replacement process may be invoked to correct the situation. For example, if a previously valid replica becomes inaccessible due to a failure of the device on which it was stored, the failed device may be replaced in the system, and another instance of the replica may be written to the replacement device. In some systems, each replica need not correspond to an exact copy of the object data. For example, in some object-redundant storage systems, an object may be divided into a number of portions or “shards” according to a redundant encoding scheme (such as a parity, error correction code or other scheme), such that the object data may be recreated from fewer than all of the generated portions. Typically, object-redundant storage systems may be also seek to improve performance characteristics, such as latency, throughput or availability.
While embodiments are described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that embodiments are not limited to the embodiments or drawings described. It should be understood, that the drawings and detailed description thereto are not intended to limit embodiments to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description or the claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include”, “including”, and “includes” mean including, but not limited to.